//
// Created by ASUS on 2024/10/14/星期一.
//
#include<bits/stdc++.h>
using namespace std;

class Node{
public:
	int val;
	int cnt=0;
	Node(int _val,int _cnt){this->val=_val;this->cnt=_cnt;}
	~Node()=default;
	bool operator<(const Node& a)const{
		if(cnt==a.cnt) return val<a.val;
		return cnt<a.cnt;
	}
};
class Solution {
public:
	vector<long long> findXSum(vector<int>& nums, int k, int x) {
		int n=nums.size();
		vector<long long> ans(n-k+1);
		set<Node> L,R;//L存放前x大节点,R作为后备军
		unordered_map<int,int> cnt;//记录每个数出现的次数
		long long res=0;//记录前x个大节点的和

		auto add=[&](int a){
			Node p(a,cnt[a]);
			if(p.cnt==0){//窗口没有这个值了，无需操作，直接返回
				return;
			}
			if(!L.empty()&&*L.begin()<p){
				res+=1LL*p.val*p.cnt;
				L.insert(p);
			}else{
				R.insert(p);
			}
		};

		auto del=[&](int a){
			Node p(a,cnt[a]);
			if(p.cnt==0){//窗口没这个值，无需操作
				return;
			}
			auto it=L.find(p);
			if(it!=L.end()){
				res-=1LL*p.val*p.cnt;
				L.erase(it);
			}else{
				R.erase(p);
			}
		};

		auto L2R=[&](){
			auto p=*L.begin();
			res-=1LL*p.val*p.cnt;
			L.erase(p);
			R.insert(p);
		};

		auto R2L=[&](){
			auto p=*R.rbegin();
			res+=1LL*p.val*p.cnt;
			R.erase(p);
			L.insert(p);
		};

		for(int i=0;i<n;i++){
			del(nums[i]);//因为不能直接修改节点的cnt，所以只能先删除再添加
			cnt[nums[i]]++;
			add(nums[i]);
			int l=i-k+1;
			if(l<0) continue;

			while(!R.empty()&&L.size()<x){//L的大小没有超过x，就把R中的节点放入L
				R2L();
			}
			while(L.size()>x){//L的大小超过x，就把L中的节点放入R
				L2R();
			}
			ans[l]=res;
			del(nums[l]);
			cnt[nums[l]]--;
			add(nums[l]);
		}
		return ans;
	}
};